package disclog;

public class PollardRho {
	static int n = 1018, N = n + 1, alpha = 2, beta = 5;
	
	static int[] newXAB(int x, int a, int b)
	{
		int r[] = new int[3];
		
		switch(x % 3)
		{
		case 0:
			r[0] = x * x % N;
			r[1] = a * 2 % n;
			r[2] = b * 2 % n;
			break;
		case 1:
			r[0] = x * alpha % N;
			r[1] = (a + 1) % n;
			r[2] = b;
			break;
		case 2:
			r[0] = x * beta % N;
			r[1] = a;
			r[2] = (b + 1) % n;
			break;
		}
		
		return r;
	}
	
	public static void main(String args[])
	{
		int x = 1, a = 0, b = 0;
		int X = x, A = a, B = b;
		int[] r = null;
		
		for(int i = 1; i < n; ++i)
		{
			r = newXAB(x, a, b); x = r[0]; a = r[1]; b = r[2];
			r = newXAB(X, A, B); X = r[0]; A = r[1]; B = r[2];
			r = newXAB(X, A, B); X = r[0]; A = r[1]; B = r[2];
			
			System.out.println("i = " + i + ", x = " + x + ", a = " + a
					+ ", b = " + b + ", X = " + X + ", A = " + A
					+ ", B = " + B);
			
			if(x == X) break;
		}
	}
}
